import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;


/**
 * 隐马尔可夫模型
 * @author kami
 *
 */
public class ViterbiStart
{
    //内部类，用于接受viterbi方法返回值，保存隐藏状态序列和状态映射
    public class HidenStateSequenAndMap{
        private String[] hiddenSequence;
        private HashMap<Integer,String> hiddenStateIndex;

        public String[] getHiddenSequence() {
            return hiddenSequence;
        }

        public void setHiddenSequence(String[] hiddenSequence) {
            this.hiddenSequence = hiddenSequence;
        }

        public HashMap<Integer, String> getHiddenStateIndex() {
            return hiddenStateIndex;
        }

        public void setHiddenStateIndex(HashMap<Integer, String> hiddenStateIndex) {
            this.hiddenStateIndex = hiddenStateIndex;
        }

    }
    //region 维特比算法 根据观察状态序列和已知的隐马尔可夫模型 返回最可能的隐藏状态序列
    // 比如观察序列产生ACGTCGCGCTTATATA序列的状态序列12321232123以状态3位结束状态的概率
    public HidenStateSequenAndMap viterbi(ArrayList<Character> observedSequence,ArrayList<String[]> hmmModle)
    {
        //创建hidenStateSequenAndMap对象，用来接收返回值
        HidenStateSequenAndMap hidenStateSequenAndMap = new HidenStateSequenAndMap();
        //region 观察序列，隐藏状态序列，隐藏状态概率，前驱隐藏状态概率 矩阵的初始化，并转入相应的log space
        //初始概率向量,概率相同，可以自定义初始状态的概率
        int viewSort,stateNumber;
        char[] viewChar;
        //double[]
        stateNumber = Integer.valueOf(hmmModle.get(0)[0]);//状态个数
        viewSort = Integer.valueOf(hmmModle.get(0)[1]);//观察字符种类个数
        viewChar = hmmModle.get(0)[2].toCharArray();//观察字符种类数组，如[0] =A,[1]=C,[2]=G,[3]=T

        int fCount=0;
        double[] logFirstTransStateD = new double[stateNumber];//存放初始转态概率
        for (String s:hmmModle.get(1))
        {
            logFirstTransStateD[fCount] = Math.log(Double.valueOf(s)) / Math.log(2);
            fCount++;
        }

        //状态转移概率矩阵，方针，4种情况 0-0,0-1；1-1,1-0   转入log space
        double[][] logTransStateArray2D = new double[stateNumber][stateNumber];
        for (int i=0;i < stateNumber;i++){
            for (int j = 0;j<stateNumber;j++){
                logTransStateArray2D[i][j] = Math.log(Double.valueOf(hmmModle.get(i+2)[j])) / Math.log(2);
                //logTransStateArray2D[i+1][j] = Math.log(Double.valueOf(hmmModle.get(3)[j])) / Math.log(2);
            }
        }

        //混淆矩阵，确定状态后选择某一个选项的概率，每种状态只有两种选择，比如说在特定状态下选择A或者B的概率
        //状态0偏向于AT，状态1偏向于CG
        double[][] logChooseItemArray2D = new double[stateNumber][viewSort];
        for (int i=0;i<stateNumber;i++){
            for (int j=0;j<viewSort;j++){
                logChooseItemArray2D[i][j] = Math.log(Double.valueOf(hmmModle.get(i+2)[j+stateNumber])) / Math.log(2);
            }
        }

        //隐藏状态索引，3种状态，对应S(0)、S(1)、S(2)  代表状态1、2、3，使用HashMap存储，key-value对，键值对
        HashMap<Integer, String> hiddenStateIndex = new HashMap<>();
        for (int i=0;i<stateNumber;i++) {
            hiddenStateIndex.put(i,String.valueOf(i));
        }
        hidenStateSequenAndMap.setHiddenStateIndex(hiddenStateIndex);  //给hidenStateSequenAndMap的Map赋初值，返回对象中的第一个返回值


        //观察状态索引，2种选择和上面的混淆矩阵B对应，放置都有哪些观察的字符，不重复，如ACGT
        HashMap<Character, Integer> observableStateIndex = new HashMap<>();
        int viewCharIndex = 0;
        for (char s:viewChar) {
            observableStateIndex.put(s,viewCharIndex++);
        }
        //endregion

        //region 观察序列，隐藏状态序列，隐藏状态概率，前驱隐藏状态概率 矩阵的长度声明与初始化
        int observedSequenceSize = observedSequence.size();  //观察序列长度
        String[] hiddenSequence = new String[observedSequenceSize];//隐藏状态序列初始化，根据观察序列的长度

        //int  = stateNumber;  //状态转移矩阵长度
        //hiddenStateProbabilityTJ[t][j]表示t时刻最可能生成O(0) O(1) ... O(t)的观察序列的以状态j为结尾的隐藏状态序列出现的概率，
        // 即选择当前状态J的概率，J = 0 或 1
        double[][] hiddenStateProbabilityTJ = new double[observedSequenceSize][stateNumber]; //本例中为 100万 * 2的二维数组
        //一个前驱数组 preStateProbability[t][j]表示以状态j为结尾的概率最大的隐藏状态序列中j的前一个状态的概率
        int[][] preStateProbability = new int[observedSequenceSize][stateNumber];  //应该是100万 * 2 的二维数组，
        //endregion

        //region 根据观察序列第一个字符初始化隐藏状态概率矩阵[0][i]，前驱隐藏状态概率矩阵[0][i]设置为0，因为不存在
        //初始化，状态转移概率矩阵遍历，stateTranslateSize = 2 行长度
        for(int i = 0; i < stateNumber; i++)
        {
            int index = observableStateIndex.get(observedSequence.get(0));//根据观察字符序列下标获得该字符，并利用HashMap的键得到其值，即对应的“值”即索引如0,1,2,3
                                                                         //observableStateIndex.put("O(0)", 0);observableStateIndex.put("O(1)", 1);
            //在初始状态下，选择到观察序列字符的第一位的概率赋值     0状态 选择 A；1状态 选择A；2状态选择A
            //概率的乘法转化为 对数的加法
            hiddenStateProbabilityTJ[0][i] = logFirstTransStateD[index] + logChooseItemArray2D[index][i];
        }

        for(int i = 0; i < stateNumber; i++)
        {    //一个前驱数组 predecessor[t][j]表示以状态j为结尾的概率最大的隐藏状态序列中j的前一个状态
            preStateProbability[0][i] = 1;        //第一个状态之前的状态随意设置，用不到
        }
        //endregion

        //region 观察字符序列，遍历状态矩阵，记录最大概率产生该观察序列的状态索引
        for(int t = 1; t < observedSequenceSize; t++)
        {      //遍历字符观察序列
            for(int j = 0; j < stateNumber; j++)
            {                 //遍历状态序列
                double max = -100000000;                                     //设置临时最大值，初始化为0
                for(int i = 0; i < stateNumber; i++)
                {//遍历状态序列,选择其中某个状态下选择到当前观察字符的最大概率
                    double stateItemProbability = hiddenStateProbabilityTJ[t - 1][i] + logTransStateArray2D[i][j];
                    if(stateItemProbability> max)
                    {   max = stateItemProbability;
                        preStateProbability[t][j] = i;          //记录概率最大的状态索引
                    }
                }
                int index = observableStateIndex.get(observedSequence.get(t));  //根据观察字符序列下标获得该字符，并利用HashMap的键得到其值，即对应的“值”
                //上面确定好最佳状态概率max后，进一步更新以j状态结尾的隐藏状态序列出现的概率，每次越乘越小，需要转入log space 来避免内存泄露
                hiddenStateProbabilityTJ[t][j] = max + logChooseItemArray2D[j][index];
            }
        }
        //endregion

        //region 记录每步的最大概率，累加起来（乘法转为log加法），并记录最后一个状态的索引
        //max就是生成整个观察状态序列的最可能的隐藏状态序列的概率
        //lastHiddenIndex用来表示这最可能的隐藏状态序列的最后一个隐藏状态
        double max = 0;
        int lastHiddenIndex = 0;
        for(int i = 0; i<stateNumber;i++)     //遍历状态转移矩阵
        {
            if(hiddenStateProbabilityTJ[observedSequenceSize - 1][i] > max)     //如果最后其中一个隐藏状态的概率 > max
            {
                max = hiddenStateProbabilityTJ[observedSequenceSize - 1][i];       //
                lastHiddenIndex = i;                //确定最后一个隐藏状态的下标，然后可以根据下标在其HashMap中查找到对应的状态
            }
        }
        //endregion

        //region 回溯出最可能生成观察状态序列的隐藏状态序列的每一个隐藏状态 放入hiddenSequence
        hiddenSequence[observedSequenceSize - 1] = hiddenStateIndex.get(lastHiddenIndex);  //获得最后一个隐藏状态
        int curHiddenIndex = lastHiddenIndex;                                                  //设置当前隐藏状态索引为最后一个隐藏状态的索引
        for(int t = observedSequenceSize - 1; t >= 1; t--)                               //从后向前遍历观察序列，从最后一个到第一个，
        {                                                                                   // 不包括第 0 个，在内在循环中是从倒数第二个开始赋值
            //一个前驱数组 predecessor[t][j]表示以状态j为结尾的概率最大的隐藏状态序列中j的前一个状态
            hiddenSequence[t - 1] = hiddenStateIndex.get(preStateProbability[t][curHiddenIndex]);
            //把前一个状态的索引赋给当前索引，因为predecessor[t][curHiddenIndex]表示前一个状态索引
            curHiddenIndex = preStateProbability[t][curHiddenIndex];
        }
        //endregion
        hidenStateSequenAndMap.setHiddenSequence(hiddenSequence);
        return hidenStateSequenAndMap;
    }
    //endregion

    public static void main(String[] args)
    {
        ArrayList<Character> characterArrayList;    //初始化字符数组，用来接收观察序列
        characterArrayList = Utils.readFileToCharacterList(args[0]);    //读入观察字符数据，并转化为字符数组list   "D:\\EE6435\\homework\\HW3\\src\\example.txt"
        //读入hmm 模型文件，其中包括
        // 0.隐藏状态个数，观察字符种类个数，观察字符种类，
        // 1.初始隐藏状态概率，
        // 2.状态转移矩阵，
        // 3.发射矩阵
        ArrayList<String[]> hmmModle = Utils.readHmmFileToStringArray(args[1]);
        ViterbiStart viterbiStart = new ViterbiStart();
        HidenStateSequenAndMap hidenStateSequenAndMap = viterbiStart.viterbi(characterArrayList,hmmModle);//执行维特比算法，其他矩阵在viterbi方法里初始化，之后可以优化
        String[] hiddenSequence = hidenStateSequenAndMap.getHiddenSequence();
        HashMap<Integer,String> hiddenStateIndex = hidenStateSequenAndMap.getHiddenStateIndex();
        //hiddenStateIndex.size()
        //region 打印隐藏状态下标
        int hiddenStateIndexSize = hiddenStateIndex.size();
        int hiddenSenquenceSize = hiddenSequence.length;
        //判断第0个隐藏状态是哪种
        int countTotal = 1;
        int count1 = 1;

        for (int i=1;i<hiddenSenquenceSize;i++){
            if ((i-1) == 0){
                System.out.print(1);
            }
            if (hiddenSequence[i-1] != hiddenSequence[i]){
                System.out.print(" -- "+(i));countTotal++;
                for(int j = 0; j<hiddenStateIndexSize;j++){
                    if (hiddenSequence[i-1] == hiddenStateIndex.get(j))
                    {
                        System.out.println("  "+hiddenStateIndex.get(j));
                        if (hiddenStateIndex.get(j).equals("1") ){
                            count1++;
                        }

                    }
                }
                System.out.print(i+1);
            }
            if (i == hiddenSenquenceSize-1){
                System.out.print(" -- "+(i+1));
                for(int j = 0; j<hiddenStateIndexSize;j++){
                    if (hiddenSequence[i] == hiddenStateIndex.get(j))
                        System.out.println("  "+hiddenStateIndex.get(j));
                }
            }

        }
        System.out.println("State1: "+count1);
        System.out.print("total: "+countTotal);
        //endregion

        //region 将读进来的example的字符List转化为 字符数组，并且大写置为1，小写置为0
//        char[] example = new char[characterArrayList.size()];
//        int k=0;
//        for (char s:characterArrayList)
//        {
//            if (s >= 97){
//                example[k] = '0';
//                k++;
//            }
//            else {
//                example[k] = '1';
//                k++;
//            }
//        }
        //endregion

        //region 打印example字符数组1 0，的下标
//        if (example[0] == '0')
//        {
//            System.out.print(" S0 "+0);
//        }else System.out.print(" S1 "+0);
//        int count = 0;
//        for (int i = 1;i<example.length;i++)
//        {
//            if (example[i-1] != example[i]){
//                    switch (example[i-1])
//                    {
//                        case '0':
//                            System.out.println(" --  "+ (i-1));
//                            System.out.print(" S1 "+i);
//                            count++;
//                            break;
//                        case '1':
//                            System.out.println(" --  "+ (i-1));
//                            System.out.print(" S0 "+i);
//                            break;
//                        default:
//                            break;
//                    }
//            }
//            if (i == example.length-1)
//            {
//                System.out.print(" -- "+i);
//            }
//        }
//        System.out.println("S1共计："+count);
        //endregion

        //输出隐藏状态序列到本地文件
        //Utils.writeToFile(hiddenSequence);

    }
}